Department of Mathematicscoretheory

DESIGN AND ANALYSIS OF ALGORITHMS

DSE 2223

Syllabus

01Fundamentals of Algorithms, Important Problem Types, Analysis of algorithm efficiency
02Analysis Framework: Asymptotic Notations and Basic Efficiency Classes, Mathematical Analysis of Non recursive and Recursive Algorithms
03Brute force Techniques, Divide and Conquer, Decrease and Conquer: Insertion Sort, Depth First Search, Breadth First Search, Topological Sorting
04Transform and Conquer: Pre-sorting, BST, Heapsort
05Space and Time trade-offs: Input Enhancement in String Matching
06Dynamic Programming: Warshall's and Floyd's Algorithms, The Knapsack Problem
07Greedy Techniques: Prim's, Kruskal's and Dijkstra's Algorithm, Huffman Trees
08Coping with limitations of algorithmic power, P, NP, and NP-complete Problems, Backtracking: n–Queens problem, Hamiltonian Circuit Problem, Subset–Sum Problem
09Branch and Bound: Assignment Problem, Knapsack Problem, TSP

Anany Levitin, Introduction to the Design and Analysis of Algorithms, (3e), Pearson Education, 2011
Ellis Horowitz and Sartaj Sahni, Computer Algorithms/C++, (2e), University Press, 2008
Thomas H. Cormen, Charles E. Leiserson, Ronal L, Rivest, Clifford Stein, Introduction to Algorithms, (3e), PHI, 2009

Credits Structure

2Lecture

1Tutorial

0Practical

3Total